package com.fadis.data.zset2;


import java.util.*;

/**
 * 利用java提供的ConcurrentSkipListMap实现redis里zset的接口
 * 问题：
 * 1 有些接口的时间复杂度可能达不到
 * 2 ConcurrentSkipListMap的key必须配套一个Comparator，而且判断key是否存在，是用compareTo和equals同时判断，
 * 这一点有点蛋疼，也就是你要给一个key更改score，必须先找到之前的score，构造一个key，找到之前的并删掉才行
 * -- 所以感觉ConcurrentSkipListMap这个东西没啥大用，不如直接用TreeMap【TreeMap也tm一样！两个key必须同时equals和compare都相等了，才是同一个key】
 *
 * 所以又考虑用一个Map<String, score>和一个TreeMap<score, String>
 */
public class MyZSet {

    public static void main(String[] args) {
//        MyZSet zset = new MyZSet();
//        zset.insert(2, "b");
//        zset.insert(1, "a");
//        zset.insert(3, "c");
//        zset.insert(4, "a");
//        for (ZSetItem k: zset.map.keySet()){
//            System.out.println(k.value + "==>" + k.score + "==>"+ zset.map.get(k));
//        }
//
//        ZSetItem item1 = new ZSetItem("a", 1);
//        ZSetItem item2 = new ZSetItem("a", 2);
//        System.out.println(zset.map.containsKey(item1));
//        System.out.println(zset.map.containsKey(item2));
//        System.out.println(comparator.compare(item1, item2));
//        System.out.println(item1.equals(item2));
//        System.out.println(item1.hashCode() == item2.hashCode());

    }

//    private static Comparator<ZSetItem> comparator = new Comparator<ZSetItem>() {
//        @Override
//        public int compare(ZSetItem o1, ZSetItem o2) {
//            if(Math.abs(o1.score - o2.score) <= 1e-6) return o1.value.compareTo(o2.value);
//            if (o1.score > o2.score) return 1;
//            return -1;
//        }
//    };

    TreeMap<Double, String> scoreMap = new TreeMap<>(); // 保证按score排序
    TreeMap<String, Double> dataMap = new TreeMap<>(); // 保证按data的字典序排序

    // 往跳跃表中插入一个新节点   0新增 1覆盖 -1已存在且score不变，没动
    public int insert(double score, String obj){
        boolean replace = false;
        if(dataMap.containsKey(obj)){
            Double oldScore = dataMap.get(obj);
            if(oldScore.equals(score)){
                return -1;
            } else{
                dataMap.remove(obj);
                scoreMap.remove(oldScore);
                replace = true;
            }
        }

        // 这才真正插入
        dataMap.put(obj, score);
        scoreMap.put(score, obj);
        return replace ? 1 : 0;
    }

    // 删除节点函数，供zslDelete、zslDeleteByScore和zslDeleteByRank函数调用
    // void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update);
//    public void delete(ZSetItem node){
//
//    }

    // 从从跳跃表中删除一个分值score、保存对象为obj的节点
    // 跳表需要score来快速定位嘛，但这里两个map的方案其实不需要score了
    public int delete(double score, String obj){
        if(dataMap.containsKey(obj)){
            Double oldScore = dataMap.get(obj);
            dataMap.remove(obj);
            scoreMap.remove(oldScore);
            return 1;
        }
        return 0;
    }

    public boolean contains(String obj){
        return dataMap.containsKey(obj);
    }

    //  在跳跃表中删除所有分值在给定范围range内的节点
    // 跳表可以快速找到两个node，然后利用链表指针删掉这段链表，两个map似乎做不到这么快！
    // -- map可以快速找到score，但找不到两个score中间的score，这是个问题
    // -- 有办法了，找到min到max的子树！并且subMap返回的是个视图，可以认为节省内存
    public long deleteRangeByScore(double min, double max){
        NavigableMap<Double, String > subMap = scoreMap.subMap(min, true, max, true);
        if(subMap == null || subMap.size() == 0) return 0;
        for(Double score: subMap.keySet()){
            String data = subMap.get(score);
            scoreMap.remove(score);
            dataMap.remove(data);
        }
        return subMap.size();
    }

    //  在跳跃表中删除给定排序范围的节点
    // redis跳表可以根据span快速找到排序范围，两个map似乎做不到这么快！只能遍历
    public long deleteRangeByRank(long min, long max){
        int i = -1;
        int deleteCount = 0;
        for (Double score: scoreMap.keySet()){
            i++;
            if(i >= min && i <= max){
                String data = scoreMap.get(score);
                scoreMap.remove(score);
                dataMap.remove(data);
                deleteCount++;
            }
            if(i == max) break;
        }
        return deleteCount;
    }

    //  删除成员对象值在指定字典序范围的节点
    public long deleteRangeByLex(long min, long max){
        int i = -1;
        int deleteCount = 0;
        for (String data: dataMap.keySet()){
            i++;
            if(i >= min && i <= max){
                Double score = dataMap.get(data);
                scoreMap.remove(score);
                dataMap.remove(data);
                deleteCount++;
            }
            if(i == max) break;
        }
        return deleteCount;
    }

    // 如果range给定的数值范围包含在跳跃表的分值范围则返回1，否则返回0
    // int zslIsInRange(zskiplist *zsl, zrangespec *range);
    public int isInRange(double min, double max){
        double[] limit = getMinAndMax();
        if(min >= limit[0] && max <= limit[1]) return 1;
        return 0;
    }

    private double[] getMinAndMax(){
        double[] r = new double[2];
        r[0] = 0;
        r[1] = 0;
        int i = -1;
        for (Double score: scoreMap.keySet()){
            i++;
            if(i == 0) r[0] = score;
            if(i == scoreMap.size() - 1) r[1] = score;
        }
        return r;
    }

    // 返回跳跃表中第一个分值score在range指定范围的节点
    public String firstInRange(double min, double max){
        for (Double score: scoreMap.keySet()){
            if(score >= min && score <= max) {
                return scoreMap.get(score);
            }
        }
        return null;
    }
    // 返回跳跃表中最后一个分值score在range指定范围的节点
    public String lastInRange(double min, double max){
        boolean hasRange = false;
        for (Double score: scoreMap.keySet()){
            if(score >= min && score <= max) {
                hasRange = true;
            }else{
                if(hasRange) return scoreMap.get(score);
            }
        }
        return null;
    }

    // 返回指定元素在跳跃表中的排位
    public long getRank(String obj){
        if(!dataMap.containsKey(obj)) return -1;
        Double score = dataMap.get(obj);

        int i = -1;
        for (Double s: scoreMap.keySet()){
            i++;
            if(s.equals(score)) return i;
        }
        return -1;
    }

    // 返回指定排位上的节点
    public String getElementByRank(long rank){
        if(rank > scoreMap.size()) return null;
        Long i = -1L;
        for (Double s: scoreMap.keySet()){
            i++;
            if(i.equals(rank)) return scoreMap.get(s);
        }
        return null;
    }


//    private int getRandomLevel(){
//        return random.nextInt(ZSKIPLIST_MAXLEVEL); // [0, 31]
//    }

}
